/*
Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo
*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

vector<int> getRepeat(int nums[], int size)
{
    int num1, num2, count1 = 0, count2 = 0;
    vector<int> ans;
    for (int i = 0; i < size; i++) {
	if (num1 == nums[i]) {
	    count1++;
	} else if (num2 == nums[i]) {
	    count2++;
	} else if (count1 == 0) {
	    count1 = 1;
	    num1 = nums[i];
	} else if (count2 == 0) {
	    count2 = 1;
	    num2 = nums[i];
	} else {
	    count1--;
	    count2--;
	}
    }
    cout << num1 << " " << num2 << endl;
    return ans;
}

int main(int argc, char **argv)
{
    int nums[] = {1,3,5,7,1,3,1,5,7,1,1,3,7,3,1,1,7,3,7,1,3,1,7};
    vector<int> ans = getRepeat(nums, sizeof(nums)/sizeof(int));
    for (int i = 0; i < ans.size(); i++)
	cout << ans[i] << " ";

}
